package bfs

func openLock(deadends []string, target string) int {
    if "0000" == target {
        return 0
    }
    dead := map[string]bool{}
    for _, deadend := range deadends {
        dead[deadend] = true
    }
    if dead["0000"] {
        return -1
    }
    step := 0
    q := []string{"0000"}
    seen := map[string]bool{"0000" : true}

    for len(q) > 0 {
        step++
        size := len(q)
        for i := 0; i < size; i++ {
            status := q[0]
            q = q[1:]
            for _, nextStatus := range get(status) {
				if !dead[nextStatus] && !seen[nextStatus] {
					if nextStatus == target {
						return step
					}
					q = append(q, nextStatus)
					seen[nextStatus] = true
				}
            }
        }
    }
	return -1
}

func numPrev(x byte) byte {
	if x == '0' {
		return '9'
	}
	return x - 1
}

func numSucc(x byte) byte {
	if x == '9' {
		return '0'
	}
	return x + 1
}

func get(status string) []string {
	res := make([]string, 0, 8)
	for i := 0; i < 4; i++ {
		res = append(res, status[:i] + string(numPrev(status[i])) + status[i+1:])
		res = append(res, status[:i] + string(numSucc(status[i])) + status[i+1:])
	}
	return res
}